1678D - Tokitsukaze and Meeting - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define all(v) v.begin(), v.end()
#define done(x){ cout << x << endl;return;}
#define f(i, n) for (int i = 0; i < n; i++)
#define f1(i, n) for (int i = 1; i < n; i++)
const ll mod = 1e9 + 7;
const ll N = 2e5 + 1;
void solve(){
    ll n,m;
    cin>>n>>m;
    string str;
    cin>>str;
    ll frr1[n*m+1],frr2[n*m+1];
    ll f[n*m+1];
    memset(frr1,0,sizeof frr1);
    memset(frr2,0,sizeof frr2);
    memset(f,0,sizeof f);
    ll cnt=0;
    f(i,n*m){
        if(str[i]=='1'){
            if(!f[i%m]){
                cnt++;
            }
            f[i%m]++;
        }
        frr1[i]=cnt;
    }
    cnt=0;
    f(i,n*m){
        if(i>=m){
            cnt-=(str[i-m]=='1');
        }
        cnt+=(str[i]=='1');
        frr2[i]=((i-m>=0)?frr2[i-m]:0)+((!cnt==0));
    }
    f(i,n*m){
        cout<<frr1[i]+frr2[i]<<" ";
    }
    cout<<endl;
    return ;
}
int main(){
    ll t;
    t = 1;
    scanf("%lld",&t);
    while (t--)
        solve();
    return 0;
}